package com.xqx.quickSort;

public class QuickSort {
    public static void quick_sort(int[] a,int l,int r){
        if (l>=r)
            return;

        int i=l;int j=r;int key=a[l];  //选择第一个数作为key
        while (i<j){
            while (i<j && a[j]>=key)//从右向左找第一个小于key的值
                j--;
            if (i<j){
                a[i]=a[j];
                i++;
            }
            while (i<j && a[i]<key)  //从左向右找第一个大于key的值
                i++;
            if (i<j){
                a[j]=a[i];
                j--;
            }
        }

        //i==j
        a[i]=key;
        quick_sort(a,l,i-1);  //递归调用
        quick_sort(a,i+1,r); //递归调用
    }
}
/*
基本思想：（分治）

        先从数列中取出一个数作为key值；
        将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
        对左右两个小数列重复第二步，直至各区间只有1个数。*/
